package week12.EXP3.cn.edu.besti.cs1723.TCM2319;

import java.util.ArrayList;

public class Searching {
    //  线性查找
    public static Comparable linearSearch(Comparable[] data,Comparable target)
    {
        int index = 0;
        Comparable result = null;
        while (result==null && index < data.length)
        {
            if (data[index].compareTo(target)==0){
                result = data[index];
            }
            else {
                index++;
            }
        }
        return result;
    }
//    public static Comparable binarySearch(Comparable[] data, Comparable target)
//    {
//        boolean found = false;
//        int midpoint = (0 + data.length) / 2;  // determine the midpoint
//
//        if (data[midpoint].compareTo(target) == 0) {
//            found = true;
//        } else if (data[midpoint].compareTo(target) > 0)
//        {
//            if (min <= midpoint - 1) {
//                found = binarySearch(data, min, midpoint - 1, target);
//            }
//        }
//
//        else if (midpoint + 1 <= max) {
//            found = binarySearch(data, midpoint + 1, max, target);
//        }
//
//        return found;
//    }
    //  二分查找
    public static Comparable BinarySearch_non_recursion(Comparable[] data,Comparable target){
        int min,max,midpoint;
        min = 0;max = data.length-1;
        Comparable result = null;
        while (result==null&&min<=max){
            midpoint = (min + max) / 2;
            if (data[midpoint].compareTo(target)==0){
                result = data[midpoint];
            }
            if (data[midpoint].compareTo(target)>0){
                max = midpoint - 1;
            }
            if (data[midpoint].compareTo(target)<0){
                min = midpoint + 1;
            }
        }
        return result;
//        if (data[midpoint].compareTo(target) == 0) {
//            found = true;
//        } else if (data[midpoint].compareTo(target) > 0)
//        {
//            if (min <= midpoint - 1) {
//                found = binarySearch(data, min, midpoint - 1, target);
//            }
//        }
//
//        else if (midpoint + 1 <= max) {
//            found = binarySearch(data, midpoint + 1, max, target);
//        }
//
//        return found;
    }
    public static Comparable BinarySearch_recursion(Comparable[] data,int min,int max,Comparable target){
        int midpoint = (max + min) / 2;
        Comparable result = null;
        while (result!=null||min>max){
            return result;
        }
        if (data[midpoint].compareTo(target)==0){
            result = data[midpoint];
            return result;
        }
        if (data[midpoint].compareTo(target)>0){
            return BinarySearch_recursion(data,min,midpoint-1,target);
        }
        if (data[midpoint].compareTo(target)<0){
            return BinarySearch_recursion(data,midpoint+1,max,target);
        }

        return result;
    }
    //  插值查找
    public static String InsertionSearch(int[] data,int min, int max,int target) {
        while (max<=min){
            return null;
        }
        int midpoint = min + (target - data[min]) / (data[max] - data[min]) * (max - min);
        String result = null;

        if (data[midpoint] == target) {
            result = String.valueOf(data[midpoint]);
            return result;
        }
        else
            if (data[midpoint] > target) {
                return InsertionSearch(data, min, midpoint - 1, target);
            }
            else {
                return InsertionSearch(data, midpoint + 1, max, target);
            }
    }
    //  斐波那契查找
    public static class FibonacciSearch{
        public final static int max_size = 20;
        public static int[] Fibonacci(){
            int[] F = new int[max_size];
            F[0] = 0;
            F[1] = 1;
            for(int i=2;i<max_size;++i) {
                F[i]=F[i-1]+F[i-2];
            }
            return F;
        }
        public static String FibonacciSearch(int []data,int target){
            int min = 0;
            int max = data.length-1;
            int mid = 0;
            String result;
            int k = 0;   // 斐波那契分割数值下标
            int i = 0;   // 序列元素个数
            int[] F = Fibonacci();    // 获取斐波那契数列
            // 获取斐波那契分割数值下标
            while (data.length > F[k] - 1) {
                ++k;
            }
            // 创建临时数组
            int[] temp = new int[F[k] - 1];
            for (int j = 0; j < data.length;j++){
                temp[j] = data[j];
            }
            for (int j : temp) {
                System.out.print(j + " ");
            }
            System.out.println();
            while (min <= max) {
                // min：起始位置
                // 前半部分有f[k-1]个元素，由于下标从0开始
                // 则-1 获取 黄金分割位置元素的下标
                mid = min + F[k - 1] - 1;

                if (temp[mid] > target) {
                    // 查找前半部分，高位指针移动
                    max = mid - 1;
                    // （全部元素） = （前半部分）+（后半部分）
                    // f[k] = f[k-1] + f[k-1]
                    // 因为前半部分有f[k-1]个元素，所以 k = k-1
                    k = k - 1;
                } else if (temp[mid] < target) {
                    // 查找后半部分，高位指针移动
                    min = mid + 1;
                    // （全部元素） = （前半部分）+（后半部分）
                    // f[k] = f[k-1] + f[k-1]
                    // 因为后半部分有f[k-1]个元素，所以 k = k-2
                    k = k - 2;
                } else {
                    // 如果为真则找到相应的位置
                    if (mid <= max) {
                        result = String.valueOf(data[mid]);
                        return result;
                    } else {
                        // 出现这种情况是查找到补充的元素
                        // 而补充的元素与max位置的元素一样
                        result = String.valueOf(data[max]);
                        return result;
                    }
                }
            }
            return null;
    }
    }

    // 树表查找
    public static String Tree_table_lookup(int[] data,int target){
       LinkedBinarySearchTree linkedBinarySearchTree = new LinkedBinarySearchTree();
        String result = null;
        for (int d : data){
            linkedBinarySearchTree.addElement(d);
        }

        return String.valueOf(linkedBinarySearchTree.find(target));
    }

    // 分块查找
    public static class BlockSearch {
        public static int[] index;
        public static ArrayList[] list;
        /**
         * 初始化索引表
         * @param index
         */
        public BlockSearch(int[] index) {
            if (index != null && index.length != 0) {
                BlockSearch.index = index;
                list = new ArrayList[index.length];
                for (int i = 0; i < list.length; i++) {
                    list[i] = new ArrayList();
                }
            } else {
                throw new Error("index cannot be null or empty.");
            }
        }
        /**
         * 插入元素
         * @param value
         */
        public static void insert(int value) {
            int i = binarySearch(value);
            list[i].add(value);
        }

        /**
         * 查找元素
         * @param data
         * @return
         */
        public static String search(int data) {
            int i = binarySearch(data);
            String result = null;
            for (int j = 0; j < list[i].size(); j++) {
                if ((int)list[i].get(j) == data) {
                    result = String.valueOf(list[i].get(j));
                    return result;
                }
            }
            return result;
        }
        /**
         * 打印每块元素
         */
        public static void printAll() {
            for (int i = 1; i < list.length; i++) {
                ArrayList l = list[i];
                System.out.print("第" + i + "块:");
                for (int j = 0; j < l.size(); j++) {
                    System.out.print(l.get(j) + " ");
                }
                System.out.println();
            }
        }
        /**
         * 二分查找定位索引位置
         * @param data 要插入的值
         * @return
         */
        private static int binarySearch(int data) {
            int start = 0;
            int end = index.length-1;
            int mid = 0;
            while (start <= end) {
                mid = (start + end) / 2;
              if (data<=index[mid]) {
                  end = mid - 1;
              }
              else {
                  start = mid + 1;
              }
            }
            return start;
        }
    }
//    public static String BlockSearch(int[] index,int[] data,int target,int size){
//        int i = Search_index(index,target);
//        System.out.println("查找元素在第" + i + "块");
//        String result = null;
//        if(i>=0){
//            //  第i块的第一个元素下标
//            int j = i > 0 ? i * size : i;
//            int current_size = (i+1)*size;
//            for (int k = j; k <current_size; k++){
//                if (data[k]==target){
//                    result = String.valueOf(data[k]);
//                    return result;
//                }
//            }
////            while (j<current_size){
////                if (data[j]==target){
////                    result = String.valueOf(data[j]);
////                    return result;
////                }
////                else {
////                    j++;
////                }
////            }
//        }
//        else {
//           return null;
//        }
//        return result;
//    }
//    public static int Search_index(int[] index, int target) {
//        int low = 0;
//        int high = index.length - 1;
//        while (low <= high) {
//            int middle = (low + high) / 2;
//            if (target == index[middle]) {
//                return middle;
//            } else if (target < index[middle]) {
//                high = middle - 1;
//            } else {
//                low = middle + 1;
//            }
//        }
//        return 0;
//    }
//    public static int Search_index (int[] index,int target ){
//        if (index[0] > target){
//            return 0;
//        }
//        int i = 1;
//        while ((index[i-1]<target)&&(index[i]>target)){
//            return i;
//        }
//        return -1;
//    }
    //  哈希查找
    public static String HashSearching(int[] data,int k,int target){
        int position = target % k;
        String result = null;
        int di =1;
        while (data[position]!=0&&data[position]!=target){
            position = (position+di)%k;
            if (k-1<=di){
                break;
            }
        }
        if (data[position]==0||data[position]!=target){
            result = null;
        }
        else if(data[position]!=0&&data[position]==target) {
            result = String.valueOf(data[position]);
        }
        return result;
    }
    public static void Hashinsert(int[] data,int k,int target){
        int position = target % k;
        int di =1;
        while (data[position]!=0){
            position = (position+di)%k;
            di++;
            if (k-1<=di){
                break;
            }
        }
        data[position] = target;
    }

}
